In processing systems such as computers, the data to be utilized by a processor is stored in a main memory and control logic manages the transfer of data between the memory and the processor in response to requests issued by the processor. The data stored in the main memory generally includes both instructions to be executed by the processor and data to be operated on by the processor. For simplicity, both instructions and true data are referred to collectively herein as "data" unless the context otherwise requires. The time taken by a main memory access is relatively long in relation to operating speeds of modern processors. To address this, a cache memory with a shorter access time is generally interposed between the main memory and the processor, and the control logic manages the storage of data retrieved from the main memory in the cache and the supply of data from the cache to the processor. The cache is organized into multiple "lines", each line providing storage for a block, or line, of data from the main memory which may be many bytes in length. When the processor issues a request for data in a line N, the control logic determines whether that line is stored in the cache. If so, ie. if there is a cache hit, the data is retrieved from the cache. If not, ie. if there is a cache miss, the data must be retrieved from the main memory and the processor is stalled while this operation takes place. Since a cache access is much faster than a main memory access, it is clearly desirable to manage the system so as to achieve a high ratio of cache hits to cache misses. Increasing the size of the cache makes this task easier, but cache memory is expensive in comparison to the slower, main memory. It is therefore important to use cache memory space as efficiently as possible.
In conventional cache memory systems, a line of data retrieved from the memory following a cache miss is stored in the cache, overwriting a previously stored line which is selected for eviction by the control logic in accordance with a priority system. The priority system indicates the relative priority of lines of data stored in the cache, with low priority lines being selected for eviction before higher priority lines. The control logic implements the priority system by maintaining priority data indicative of the current priorities of the stored lines various priority systems are known, though the generally favoured technique is a Least Recently Used system where the control logic maintains data indicating relatively how recently lines stored in the cache have been accessed by the processor. The least recently used (LRU) line is selected for eviction first when space is required for a new line, and this line then becomes the most recently used (MRU) line when it is read out to the processor. Whatever the priority system employed, it is desirable to utilize the cache memory space so as to reduce processor stall time due to main memory accesses as far as possible.
In practice, the effectiveness of current cache memory systems is dependent on the nature of the processing application. For example, real time multithreaded applications, such as in a storage controller environment, have an execution profile which is unfriendly to the operation of a conventional cache. Execution of instructions in these environments is driven by external events, such as a new host I/O arriving or a disk I/O completing, and these events tend to occur in a random order. Each event calls for a particular sequence of instructions to be executed a single time. These instructions are not then executed again until the next time that event occurs. The lack of repetition means that a cache will not be effective unless an event repeats within the lifetime of lines stored in the cache. If the set of all events is large, and the code that is executed for each event is mostly unique, then the full set of code will exceed the available cache memory space. Thus, an instruction will only be executed once before it is evicted from the cache and replaced with another instruction for another event. This means that the cache is not effective in improving the instruction throughput of the processor.
One way to improve efficiency of a cache memory system is to attempt to anticipate processor requests and retrieve lines of data from the memory in advance. This technique is known as prefetching. U.S. Pat. No. 5,566,324 discloses such a memory system in which, in the event of a main cache miss, a current line is retrieved from memory and the sequentially next line is retrieved and stored in a prefetch cache. If the prefetched line is requested next by the processor, this line is then loaded to the main cache and supplied to the processor, so that a main memory access is avoided. U.S. Pat. No. 4,980,823 discloses another prefetching system which, rather than using a separate prefetch store as in U.S. Pat. No. 5,566,324, prefetches lines directly into an LRU location of the cache. Known prefetching systems can improve performance to some extent in applications where data lines are called sequentially by the processor. However, in many applications the processing requirements are more complex and the effectiveness of current prefetching systems is limited. The applications described above in relation to a storage controller provide an example. While the use of known prefetching systems in this environment will save some processor stall time for main memory accesses, ie. for the sequentially called lines within a particular section of code, this does not significantly improve the overall efficiency of the memory system.